Real-time path planning for virtual crowds in dynamic environments is a challenging issue that has many applications. Virtual crowd simulation has applications in emergency evacuation, architecture design, urban planning, personnel training, education and entertainment. In robotics, the same problem occurs in multiple-robot coordination and planning in dynamically changing physical environments. The presented work is a conceptual hybrid of three common models for virtual crowd simulation which are social force models, rule-based models and cellular automata models. Navigation of each agent within the crowd is analyzed in terms of global and local path planning strategies. As for global path planning, presented work makes use of a regional navigation graph and deploys search algorithms to find a suitable path to global goal of each agent. For local path planning, Helbing Traffic-Flow model is used to avoid obstacles and agents. Per region adaptive grids are formed from regional navigability information and a potential field is constructed for each region. For each agent, potential forces are then applied considering the local and global decisions of the subject agent. The proposed approach reduces running time complexity of previous works on global path planning and gives freedom to each agent to act independently.

DATE: 15 December, 2008, Monday@ 15:40
PLACE: EA 409